1375. Система счисления “-2”
Творец создал Вселенную
загадочным образом. При этом он использовал десятичную систему счисления и
любил круглые цифры.
Скотт Адамс
Многие знают о
системе счисления с основанием 2 (двоичная система счисления) и практически все
знают о десятичной системе счисления (система с основанием 10), а что это за
странная база с основанием "-2"? Целое число n записанное в системе
счисления с основанием "-2" это последовательность цифр (bi), записанных справа налево.
Причём каждая цифра это либо 0 либо 1 (не отрицательные цифры!), и при этом
должно выполняться равенство:
n = b0 + b1(-2) + b2(-2)2
+ b3(-2)3 + ...
Оказывается, что
любое целое число, в том числе и отрицательные числа, имеют уникальное
представление в такой системе счисления с основанием "-2". Ваша
задача - найти это представление.
Вход. В первой строке задано количество
тестов n (не более 10000). Следующие n строк содержат сами тесты, в которых
находится единственное целое число в пределах от -1000000000 до 1000000000.
Выход. Для каждого теста в отдельной строке
выведите сначала сообщение о его номере "Case #x:", а далее через
пробел представление заданного числа в системе счисления с основанием
"-2" без ведущих нулей.
|
Пример входа |
Пример выхода |
|
4 1 7 -2 0 |
Case
#1: 1 Case
#2: 11011 Case
#3: 10 Case
#4: 0 |
РЕШЕНИЕ
системы
счисления
Анализ алгоритма
Исходя из
равенства n = b0 + b1
* (–2) + b2 * (–2)2
+ b3 * (–2)3 +
… следует, что число n делится на –2
только если оно четное, а число n – b0 должно делиться на –2.
Если n четное, то положим b0 = 0 (если нечетное, то b0 = 1), делим n – b0
на –2, после чего рекурсивно продолжаем искать представление числа 
в системе счисления по
основанию –2.
Отдельно
обрабатываем случай n = 0.
Пример
Пусть n = 6. Последовательно делим n на –2 с остатком:
6 / –2 = –3,
остаток 0 Проверка: 6 =
(–3) * (–2) + 0
–3 / –2 = 2,
остаток 1 Проверка: –3 = 2
* (–2) + 1
2 / –2 = –1,
остаток 0 Проверка: 2 =
(–1) * (–2) + 0
–1 / –2 = 1,
остаток 1 Проверка: –1 = 1
* (–2) + 1
Записав впереди
1 и остатки в обратном порядке, получим запись 11010, что составляет
Реализация алгоритма
Читаем
количество тестов. Для каждого теста вводим значение n.
scanf("%d",&tests);
for(i = 0; i < tests; i++)
{
scanf("%d",&n);
Отдельно обрабатываем случай когда
n = 0.
if (!n)
{
printf("Case #%d: 0\n",i+1);
continue;
}
В строке s накапливаем цифры результата, инициализируем ее пустой строкой.
Пока 
, записываем соответствующую цифру результата bi в строку s, вычитаем из n значение bi
и делим разность n – bi на –2. То есть совершаем присваивание 
.
s = "";
while (n !=
1)
{
if (n % 2)
n -= 1, s += '1'; else
s += '0';
n /= -2;
}
Добавим в конец строки 1, обернем
ее и выведем на печать.
s += '1';
reverse(s.begin(),s.end());
printf("Case #%d: %s\n",i+1,s.c_str());
}